package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayDeque;

/*
222.完全二叉树的节点个数
 */
public class Of20210309LeetCode222 {
    /*
    给出一个完全二叉树，求出该树的节点个数。
     */
    public static void main(String[] args) {
        System.out.println(countNodes2(new TreeNode(1, new TreeNode(2, new TreeNode(4)
                , new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)))));
    }

    /*
    递归法
     */
    private static int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    /*
    迭代法
     */
    private static int countNodes2(TreeNode root) {
        if (root == null) return 0;
        ArrayDeque<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        int result = 0;
        while (!que.isEmpty()){
            TreeNode node = que.remove();
            result++;
            if (node.left!=null) que.add(node.left);
            if (node.right!=null) que.add(node.right);
        }
        return result;
    }
}
